Round-Robin ngoài các tác nhân bổ sung: Sự tồn tại và công bằng của các trạng thái cân bằng gần đúng
Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria.
Việc phân bổ công bằng các hàng hóa không thể phân chia đã thu hút được sự chú ý rộng rãi trong hai thập kỷ qua, mang lại nhiều kết quả thuật toán hay và tạo ra những câu hỏi mở đầy thách thức. Vấn đề trở nên khó khăn hơn nhiều khi có sự hiện diện của các tác nhân chiến lược. Lý tưởng nhất là người ta muốn thiết kế các cơ chế trung thực để tạo ra phân bổ đảm bảo công bằng. Tuy nhiên, trong thiết lập tiêu chuẩn mà không cần chuyển tiền, nhìn chung không thể có các cơ chế trung thực mang lại sự đảm bảo công bằng không đơn giản để nhận thấy. Gần đây, Amanatidis và cộng sự [5] đề xuất nghiên cứu các cơ chế tạo ra sự phân bổ công bằng ở trạng thái cân bằng. Cụ thể, khi các tác nhân có hàm định giá bổ sung, thuật toán Round-Robin đơn giản luôn có trạng thái cân bằng Nash thuần túy và việc phân bổ tương ứng không ghen tị với một mục (EF1) đối với các hàm định giá thực của tác nhân. Theo nghiên cứu này, các tác giả cho thấy thuộc tính nổi bật này của cơ chế Round-Robin vượt xa giả định mặc định ở trên về khả năng bổ sung. Cụ thể, các tác giả chứng minh đối với các tác nhân có hàm định giá có thể hủy bỏ (một lớp tự nhiên chứa, ví dụ: hàm bổ sung và hàm bổ sung ngân sách), cơ chế đơn giản này luôn có trạng thái cân bằng và thậm chí trạng thái cân bằng gần đúng của nó tương ứng với phân bổ gần đúng EF1 đối với hàm định giá thực của các tác nhân. Hơn nữa, các tác giả cho thấy tính công bằng gần đúng của EF1 của các điểm cân bằng gần đúng cũng đúng một cách đáng ngạc nhiên đối với lớp quan trọng của các hàm định giá mô đun phụ, mặc dù các điểm cân bằng chính xác không tồn tại!
Đọc thêm các bài viết liên quan tại thẻ Tags bên dưới